// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 定义单向链表
type ListNode struct {
	Data int
	Next *ListNode
}

// 合并K个链表
func mergeKLists(lists []*ListNode) *ListNode {
	length := len(lists)
	if length < 1 {
		return nil
	}
	if length == 1 {
		return lists[0]
	}
	num := length / 2
	left := mergeKLists(lists[:num])
	right := mergeKLists(lists[num:])
	return mergeTwoLists(left, right)
}

// 合并两个链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Data < l2.Data {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	}
	l2.Next = mergeTwoLists(l1, l2.Next)
	return l2
}

func main() {
	nodeList1 := ListNode{66, nil}
	nodeList2 := ListNode{99, nil}
	nodeList3 := ListNode{88, nil}
	nodeList4 := ListNode{55, nil}
	ListsK := []*ListNode{&nodeList1, &nodeList2, &nodeList3, &nodeList4}
	ret := mergeKLists(ListsK)
	//打印结果
	fmt.Println(ret.Data)
	if ret.Next != nil {
		fmt.Println(ret.Next.Data)
		if ret.Next.Next != nil {
			fmt.Println(ret.Next.Next.Data)
			if ret.Next.Next.Next != nil {
				fmt.Println(ret.Next.Next.Next.Data)
			}
		}
	}
}

//$ go run interview3-6.go
//55
//66
//88
//99
